home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / misc / gs261src.zip / gxht.c < prev    next >
C/C++ Source or Header  |  1993-05-13  |  13KB  |  370 lines
  1. /* Copyright (C) 1989, 1992 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* gxht.c */
  20. /* Halftone rendering routines for Ghostscript imaging library */
  21. #include "memory_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gxfixed.h"
  25. #include "gxmatrix.h"            /* for gxdevice.h */
  26. #include "gzstate.h"
  27. #include "gzdevice.h"
  28. #include "gzcolor.h"            /* requires gxdevice.h */
  29. #include "gzht.h"
  30.  
  31. extern ulong gs_next_ids(P1(uint));
  32.  
  33. /*
  34.  * We don't want to remember all the values of the halftone screen,
  35.  * because they would take up space proportional to P^3, where P is
  36.  * the number of pixels in a cell.  Instead, we pick some number N of
  37.  * patterns to cache.  Each cache slot covers a range of (P+1)/N
  38.  * different gray levels: we "slide" the contents of the slot back and
  39.  * forth within this range by incrementally adding and dropping 1-bits.
  40.  * N>=0 (obviously); N<=P+1 (likewise); also, so that we can simplify things
  41.  * by preallocating the bookkeeping information for the cache, we define
  42.  * a constant max_cached_tiles which is an a priori maximum value for N.
  43.  *
  44.  * Note that the raster for each tile must be a multiple of 32 bits,
  45.  * to satisfy the copy_mono device routine, even though a multiple of
  46.  * 16 bits would otherwise be sufficient.
  47.  */
  48.  
  49. /*** Big memory machines ***/
  50. #define max_cached_tiles_LARGE 256
  51. #define max_ht_bits_LARGE 35000
  52. /*** Small memory machines ***/
  53. #define max_cached_tiles_SMALL 25
  54. #define max_ht_bits_SMALL 1000
  55.  
  56. #if arch_ints_are_short
  57. #  define max_cached_tiles max_cached_tiles_SMALL
  58. #  define max_ht_bits max_ht_bits_SMALL
  59. #else
  60. #  define max_cached_tiles max_cached_tiles_LARGE
  61. #  define max_ht_bits max_ht_bits_LARGE
  62. #endif
  63.  
  64. typedef struct bit_tile_s {
  65.     int level;            /* the cached gray level, i.e. */
  66.                     /* the number of spots whitened, */
  67.                     /* or -1 if the cache is empty */
  68.     gx_bitmap tile;            /* the currently rendered tile */
  69. } bit_tile;
  70. typedef struct gx_ht_cache_s {
  71.     /* The following are set when the cache is created. */
  72.     byte *bits;            /* the base of the bits */
  73.     uint bits_size;            /* the space available for bits */
  74.     /* The following are reset each time the cache is initialized */
  75.     /* for a new screen. */
  76.     ht_bit *order;            /* the cached order vector */
  77.     int num_cached;            /* actual # of cached tiles */
  78.     int levels_per_tile;        /* # of levels per cached tile */
  79.     bit_tile tiles[max_cached_tiles];    /* the cached tiles */
  80.     gx_bitmap_id base_id;        /* the base id, to which */
  81.                     /* we add the halftone level */
  82. } gx_ht_cache;
  83.  
  84. /* Bit masks for whitening vector.  The high-order byte always comes */
  85. /* first.  We have to define the masks as bit16 to ensure that */
  86. /* they will be properly aligned in memory on machines that care. */
  87. typedef unsigned short bit16;
  88. #if arch_is_big_endian
  89. #  define b2(hi,lo) (hi<<8)+lo
  90. #else
  91. #  define b2(hi,lo) (lo<<8)+hi
  92. #endif
  93. private const bit16 single_bits[16] =
  94.    {    b2(0x80,0), b2(0x40,0), b2(0x20,0), b2(0x10,0),
  95.     b2(8,0), b2(4,0), b2(2,0), b2(1,0),
  96.     b2(0,0x80), b2(0,0x40), b2(0,0x20), b2(0,0x10),
  97.     b2(0,8), b2(0,4), b2(0,2), b2(0,1)
  98.    };
  99. private const bit16 mb1[1] =
  100.    {    b2(0xff,0xff) };
  101. private const bit16 mb2[2] =
  102.    {    b2(0xaa,0xaa), b2(0x55,0x55) };
  103. private const bit16 mb3[3] =
  104.    {    b2(0x92,0x49), b2(0x49,0x24), b2(0x24,0x92) };
  105. private const bit16 mb4[4] =
  106.    {    b2(0x88,0x88), b2(0x44,0x44), b2(0x22,0x22), b2(0x11,0x11) };
  107. private const bit16 mb5[5] =
  108.    {    b2(0x84,0x21), b2(0x42,0x10), b2(0x21,0x08), b2(0x10,0x84),
  109.     b2(0x08,0x42)
  110.    };
  111. private const bit16 mb6[6] =
  112.    {    b2(0x82,0x08), b2(0x41,0x04), b2(0x20,0x82), b2(0x10,0x41),
  113.     b2(0x08,0x20), b2(0x04,0x10)
  114.    };
  115. private const bit16 mb7[7] =
  116.    {    b2(0x81,0x02), b2(0x40,0x81), b2(0x20,0x40), b2(0x10,0x20),
  117.     b2(0x08,0x10), b2(0x04,0x08), b2(0x02,0x04)
  118.    };
  119. private const bit16 mb8[8] =
  120.    {    b2(0x80,0x80), b2(0x40,0x40), b2(0x20,0x20), b2(0x10,0x10),
  121.     b2(0x08,0x08), b2(0x04,0x04), b2(0x02,0x02), b2(0x01,0x01)
  122.    };
  123. #undef b2
  124. private const bit16 *multi_bits[9] =
  125.    {    0, mb1, mb2, mb3, mb4, mb5, mb6, mb7, mb8
  126.    };
  127.  
  128. /* Allocate a halftone cache. */
  129. int
  130. gx_alloc_ht_cache(gs_state *pgs)
  131. {    gs_proc_alloc_t palloc = pgs->memory_procs->alloc;
  132.     gx_ht_cache *pcache =
  133.         (gx_ht_cache *)(*palloc)(1, sizeof(gx_ht_cache),
  134.                      "alloc_ht_cache(struct)");
  135.     byte *cbits = (byte *)(*palloc)(max_ht_bits, 1,
  136.                     "alloc_ht_cache(bits)");
  137.     if ( pcache == 0 || cbits == 0 )
  138.         return_error(gs_error_VMerror);
  139.     pcache->bits = cbits;
  140.     pcache->bits_size = max_ht_bits;
  141.     pgs->ht_cache = pcache;
  142.     return 0;
  143. }
  144.  
  145. /* Construct the order vector.  order is an array of ht_bits: */
  146. /* order[i].offset contains the index of the bit position */
  147. /* that is i'th in the whitening order. */
  148. int
  149. gx_ht_construct_order(ht_bit *order, int width, int height)
  150. {    uint i;
  151.     uint size = (uint)(width * height);
  152.     int padding = (-width) & 31;
  153.     if ( (width + padding) / 8 * height > max_ht_bits )
  154.         return_error(gs_error_limitcheck);    /* can't cache the rendering */
  155.     /* Convert sequential indices to */
  156.     /* byte indices and mask values. */
  157.     for ( i = 0; i < size; i++ )
  158.        {    int pix = order[i].offset;
  159.         pix += pix / width * padding;
  160.         order[i].offset = (pix >> 4) << 1;
  161.         order[i].mask =
  162.             (width <= 8 ?
  163.              multi_bits[width][pix & 15] :
  164.              single_bits[pix & 15]);
  165.        }
  166. #ifdef DEBUG
  167. if ( gs_debug['h'] )
  168.        {    dprintf1("[h]Halftone order %lx:\n", (ulong)order);
  169.         for ( i = 0; i < size; i++ )
  170.             dprintf3("%4d: %u:%x\n", i, order[i].offset,
  171.                  order[i].mask);
  172.        }
  173. #endif
  174.     return 0;
  175. }
  176.  
  177. /* Install a new halftone in the graphics state. */
  178. void
  179. gx_ht_install(gs_state *pgs, const halftone_params *pht)
  180. {    *pgs->halftone = *pht;
  181.     /* Clear the cache, to avoid confusion in case */
  182.     /* the address of a new order vector matches that of a */
  183.     /* (deallocated) old one. */
  184.     pgs->ht_cache->order = NULL;
  185. }
  186.  
  187. /* Make the cache order current, and return whether */
  188. /* there is room for all possible tiles in the cache. */
  189. private void init_ht(P2(gx_ht_cache *, const halftone_params *));
  190. int
  191. gx_check_tile_cache(gs_state *pgs)
  192. {    const halftone_params *pht = pgs->halftone;
  193.     gx_ht_cache *pcache = pgs->ht_cache;
  194.     if ( pcache->order != pht->order )
  195.       init_ht(pcache, pht);
  196.     return pcache->levels_per_tile == 1;
  197. }
  198.  
  199. /* Determine whether a given (width, y, height) might fit into a */
  200. /* single tile. If so, return the byte offset of the appropriate row */
  201. /* from the beginning of the tile; if not, return -1. */
  202. int
  203. gx_check_tile_size(gs_state *pgs, int w, int y, int h)
  204. {    int tsy;
  205.     const gx_bitmap *ptile0 =
  206.         &pgs->ht_cache->tiles[0].tile;    /* a typical tile */
  207. #define tile0 (*ptile0)
  208.     if ( h > tile0.rep_height || w > tile0.rep_width )
  209.       return -1;
  210.     tsy = (y + pgs->phase_mod.y) % tile0.rep_height;
  211.     if ( tsy + h > tile0.size.y )
  212.       return -1;
  213.     /* Tile fits in Y, might fit in X. */
  214.     return tsy * tile0.raster;
  215. #undef tile0
  216. }
  217.  
  218. /* Load the device color into the halftone cache if needed. */
  219. private int render_ht(P4(bit_tile *, int, const halftone_params *, gx_bitmap_id));
  220. int
  221. gx_color_load(gx_device_color *pdevc, gs_state *pgs)
  222. {    int level = pdevc->halftone_level;
  223.     const halftone_params *pht;
  224.     gx_ht_cache *pcache;
  225.     bit_tile *bt;
  226.     if ( level == 0 ) return 0;    /* no halftone */
  227.     pht = pgs->halftone;
  228.     pcache = pgs->ht_cache;
  229.     if ( pcache->order != pht->order )
  230.         init_ht(pcache, pht);
  231.     bt = &pcache->tiles[level / pcache->levels_per_tile];
  232.     if ( bt->level != level )
  233.     {    int code = render_ht(bt, level, pht, pcache->base_id);
  234.         if ( code < 0 ) return code;
  235.     }
  236.     pdevc->tile = &bt->tile;
  237.     return 0;
  238. }
  239.  
  240. /* Initialize the tile cache for a given screen. */
  241. /* Cache as many different levels as will fit. */
  242. private void
  243. init_ht(gx_ht_cache *pcache, const halftone_params *pht)
  244. {    int width = pht->width;
  245.     int height = pht->height;
  246.     int size = width * height;
  247.     static int up_to_16[] =
  248.         /* up_to_16[i] = 16 / i * i */
  249.         { 0, 16, 16, 15, 16, 15, 12, 14, 16 };
  250.     int width_unit = (width <= 8 ? up_to_16[width] : width);
  251.     int height_unit = height;
  252.     uint raster = ((width + 31) >> 5) << 2;
  253.     uint tile_bytes = raster * height;
  254.     int num_cached;
  255.     int i;
  256.     byte *tbits = pcache->bits;
  257.     /* Make sure num_cached is within bounds */
  258.     num_cached = max_ht_bits / tile_bytes;
  259.     if ( num_cached > size ) num_cached = size;
  260.     if ( num_cached > max_cached_tiles ) num_cached = max_cached_tiles;
  261.     if ( num_cached == size &&
  262.          tile_bytes * num_cached <= max_ht_bits / 2
  263.        )
  264.        {    /* We can afford to replicate every tile vertically, */
  265.         /* which will reduce breakage when tiling. */
  266.         height_unit <<= 1, tile_bytes <<= 1;
  267.        }
  268.     pcache->base_id = gs_next_ids(size);
  269.     for ( i = 0; i < num_cached; i++ )
  270.        {    register bit_tile *bt = &pcache->tiles[i];
  271.         bt->level = -1;
  272.         bt->tile.data = tbits;
  273.         bt->tile.raster = raster;
  274.         bt->tile.size.x = width_unit;
  275.         bt->tile.size.y = height_unit;
  276.         bt->tile.rep_width = width;
  277.         bt->tile.rep_height = height;
  278.         tbits += tile_bytes;
  279.        }
  280.     pcache->order = pht->order;
  281.     pcache->num_cached = num_cached;
  282.     pcache->levels_per_tile = (size + num_cached - 1) / num_cached;
  283. }
  284.  
  285. /*
  286.  * Compute and save the rendering of a given gray level
  287.  * with the current halftone.  The cache holds multiple tiles,
  288.  * where each tile covers a range of possible levels.
  289.  * If the tile whose range includes the desired level is already loaded,
  290.  * we adjust it incrementally: this saves a lot of time for
  291.  * the average image, where gray levels don't change abruptly.
  292.  * Note that we will never be asked to cache levels 0 or order_size,
  293.  * which correspond to black or white respectively.
  294.  */
  295. private int
  296. render_ht(bit_tile *pbt, int level /* [1..order_size-1] */,
  297.   const halftone_params *pht, gx_bitmap_id base_id)
  298. {    ht_bit *order = pht->order;
  299.     register ht_bit *p;
  300.     register ht_bit *endp;
  301.     register byte *bits = pbt->tile.data;
  302.     int old_level = pbt->level;
  303.     if ( old_level < 0 )
  304.        {    /* The cache is empty.  Preload it with */
  305.         /* whichever of all-0s and all-1s will be faster. */
  306.         uint tile_bytes = pbt->tile.raster * pbt->tile.size.y;
  307.         if ( level >= pht->order_size >> 1 )
  308.            {    old_level = pht->order_size;
  309.             memset(bits, 0xff, tile_bytes);
  310.            }
  311.         else
  312.            {    old_level = 0;
  313.             memset(bits, 0, tile_bytes);
  314.            }
  315.        }
  316. #ifdef DEBUG
  317.     if ( level < 0 || level > pht->order_size || level == old_level )
  318.        {    lprintf3("Error in render_ht: level=%d, old_level=%d, order_size=%d=n", level, old_level, pht->order_size);
  319.         return_error(gs_error_Fatal);
  320.        }
  321. #endif
  322.     /* Note that we can use the same loop to turn bits either */
  323.     /* on or off, using xor.  We use < to compare pointers, */
  324.     /* rather than ==, because Turbo C only compares the */
  325.     /* low 16 bits for < and > but compares all 32 bits for ==. */
  326.     if ( level > old_level )
  327.         p = &order[old_level], endp = &order[level];
  328.     else
  329.         p = &order[level], endp = &order[old_level];
  330.     /* Invert bits between the two pointers */
  331.     do
  332.        {    *(bit16 *)&bits[p->offset] ^= p->mask;
  333.        }
  334.     while ( ++p < endp );
  335. #ifdef DEBUG
  336. if ( gs_debug['h'] )
  337.        {    byte *p = bits;
  338.         int wb = pbt->tile.raster;
  339.         byte *ptr = bits + wb * pbt->tile.size.y;
  340.         dprintf7("[h]Halftone cache %lx: old=%d, new=%d, w=%d(%d), h=%d(%d):\n",
  341.              (ulong)bits, old_level, level, pbt->tile.size.x,
  342.                  pht->width, pbt->tile.size.y, pht->height);
  343.         while ( p < ptr )
  344.            {    dprintf8(" %d%d%d%d%d%d%d%d",
  345.                  *p >> 7, (*p >> 6) & 1, (*p >> 5) & 1,
  346.                  (*p >> 4) & 1, (*p >> 3) & 1, (*p >> 2) & 1,
  347.                  (*p >> 1) & 1, *p & 1);
  348.             if ( (++p - bits) % wb == 0 ) dputc('\n');
  349.            }
  350.        }
  351. #endif
  352.     pbt->level = level;
  353.     pbt->tile.id = base_id + level;
  354.     if ( pbt->tile.size.y > pbt->tile.rep_height )
  355.       { /* Replicate the tile in Y.  We only do this when */
  356.         /* all the renderings will fit in the cache, */
  357.         /* so we only do it once per level, and it doesn't */
  358.         /* have to be very efficient. */
  359.         uint rh = pbt->tile.rep_height;
  360.         uint h = pbt->tile.size.y;
  361.         uint tsize = pbt->tile.raster * rh;
  362.         do
  363.           { memcpy(bits + tsize, bits, tsize);
  364.         bits += tsize;
  365.           }
  366.         while ( (h -= rh) != 0 );
  367.       }
  368.     return 0;
  369. }
  370.